一、DGI [2018]

《Deep graph infomax》

1. 目前将神经网络推广到图结构数据上已经取得了长足的进步，但是大多数成功的方法都是使用监督学习，而现实很多场景中图数据是缺乏标签信息的。此外，通常希望从大型的图中挖掘新颖或有趣的结构。因此，无监督的图学习对于很多任务至关重要。

   目前图的无监督学习的主要算法依赖于随机游走的目标（random walk-based objective），有时会进一步简化为重建邻域信息。背后的直觉是：训练编码器网络，使得在输入图中邻近的节点在embedding 空间中也是邻近的。

   尽管随机游走的方法的能力强大，但是仍然存在一些已知的限制：

   • 首先，众所周知，随机游走目标会过分强调邻近信息（aproximity information），从而忽略图的结构信息（structural information），并且性能高度依赖于超参数的选择。

   • 此外，随着基于图卷积的更强大的编码器模型的引入，还不清楚随机游走目标是否实际上提供了任何有用的信号，因为这些图卷积编码器已经施加了inductive bias，即相邻的节点具有相似的representation。

   在论文 《Deep graph infomax》 中，作者提出了一个基于互信息 （mutual information）而不是随机游走的无监督的图学习的目标。作者提出了 Deep Graph Infomax: DGI ，这是一种以无监督方式学习图结构化数据的节点representation 的通用方法。

   DGI 依赖于最大化图的 patch representation （即节点 embedding ）和相应的 high-level summary 之间的互信息 （mutual information），二者均使用已构建的图卷积网络体系结构得到。学到的 path representation 总结了目标节点为中心的子图，因此可复用于下游的 node-wise 学习任务。

   和大多数以前的使用 GCN 进行无监督学习的方法相比，DGI 不依赖于随机游走目标，并且很容易应用于 transductive learning 和 inductive learning 。该方法在各种节点分类 benchmark上表现出有竞争力的性能，有时甚至超越了监督学习的性能。

2. 最近 Mutual Information Neural Estimation: MINE 使得互信息的可扩展估计（scalable estimation）可行又实用。MINE 认为，利用神经网络的梯度下降法可以实现高维连续随机变量之间互信息的估计。具体而言，给定随机变量 $X,Z$$X,Z$ ，则它们之间的互信息定义为：

   $$I(X;Z)=\sum _{x\in X}\sum _{z\in Z}\log \frac{p(x,z)}{p(x)p(z)}p(x,z)=H(X)-H(X\mid Z)$$

   其中： $H(X)=\sum _{x}p(x)\log \frac{1}{p(x)}$$H(X) = \sum_x p(x)\log \frac{1}{p(x)}$ 为随机变量 $X$$X$ 的熵；$H(X\mid Z)=H(X,Z)-H(Z)$$H(X\mid Z)=H(X,Z)-H(Z)$ 为给定随机变量 $Z$$Z$ 的条件下随机变量 $X$$X$ 的熵。

   根据定义有 $I(X;Z)=D_{KL}(p(x,z)||p(x)p(z))$$I(X;Z) = D_{KL}(p(x,z)||p(x)p(z))$ ，其中 $D_{KL}$$D_{KL}$ 为 KL 散度。MINE 利用了 KL 散度的对偶表示，并依赖于训练一个统计网络作为样本的分类器，而样本来自于两个随机变量的联合分布（类别一）及其边际概率的乘积（类别二）。

   继 MINE 之后，Deep InfoMax: DIM 训练编码器模型，从而最大化 high-level 全局representation 和局部的部分输入（如图像的 patch）的局部representation 之间的互信息。这鼓励编码器携带在所有位置（location）都存在的信息类型（因此是全局相关的），例如图像类别标签。

   DIM 在图像数据场景中严重依赖于卷积神经网络结构。据我们所知，目前还没有工作将互信息最大化应用于图结构数据。这里我们将DIM 的思想应用到图数据，因而提出了称之为 Deep Graph Infomax: DGI 的方法。

3. 相关工作：

   • 对比方法（contrastive method）：无监督学习 representation 的一种重要方法是训练编码器，使得编码器在捕获感兴趣的representation和不感兴趣的representation 之间形成对比。例如，可以使得编码器对于 real 输入增加评分、对于 fake 输入降低评分。评分函数有很多种，但是在图数据相关论文中，常见的是分类的得分。

     DGI 也使用了对比学习，因为我们的目标是基于真实 local-global pair 对、以及负采样的 local-global pair 对进行分类。

   • 采样策略：对比学习的关键是如何采样正样本和负样本。

     • 关于无监督的 graph representation learning的先前工作依赖于局部对比损失，即强制相邻的节点具有相似的 representation 。正样本通常对应于图的short random walk 中共现的 pair 对。从语言模型的观点来看，这是将随机游走视为句子、将节点视为word 。

     • 最近的工作采用 node-anchored 采样方法，该方法的负样本主要基于随机采样。例如：有一些 curriculum-based负采样方法，它逐渐采样更靠近（closer）的负样本。或者，引入对抗方法来选择负样本。

   • 预测编码（predictive coding）：对比预测编码（contrastive predictive coding: CPC）是另一种基于互信息最大化的深度学习表示方法。和我们方法不同，CPC 和上述的图方法都是预测性的（predictive）：对比目标有效地在输入的结构之间训练了一个 predictor，如相邻节点pair 对或者节点和它的邻域。而我们的方法同时对比了图的 global 部分和 local 部分，其中 global 变量是根据所有 local 变量计算而来。

1.1 模型

1. 给定图 $\mathcal{G}=(\mathbf{X},\mathbf{A})$$\mathcal G=(\mathbf X,\mathbf A)$，其中：

   • 每个节点 $v_i$$v_i$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_i\in \mathbb R^{d_f}$ ，所有节点的特征向量组成特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d_f}$$\mathbf X\in \mathbb R^{n\times d_f}$ 。$n$$n$ 为节点数量。

   • $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ 为邻接矩阵，其中 $A_{i,j}$$A_{i,j}$ 表示节点 $v_i,v_j$$v_i,v_j$ 之间的连接权重。当 $A_{i,j}=0$$A_{i,j}=0$ 表示 $v_i$$v_i$ 和 $v_j$$v_j$ 之间不存在连接。

     这里我们假设图是无权重的，即 $A_{i,j}\in \{0,1\}$$A_{i,j}\in \{0,1\}$ 。

   我们的目标是学习一个编码器（encoder） $\mathcal{E}:{\mathbb{R}}^{n\times d_f}\times {\mathbb{R}}^{n\times n}\to {\mathbb{R}}^{n\times d}$$\mathcal E:\mathbb R^{n\times d_f}\times \mathbb R^{n\times n}\rightarrow \mathbb R^{n\times d}$ ，使得 $\mathcal{E}(\mathbf{X},\mathbf{A})=\mathbf{H}\in {\mathbb{R}}^{n\times d}$$\mathcal E(\mathbf X,\mathbf A) = \mathbf H\in \mathbb R^{n\times d}$ 。其中：$\mathbf{H}$$\mathbf H$ 为所有节点的representation 矩阵，它的第 $i$$i$ 行 ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec h}_i\in \mathbb R^d$ 为节点 $v_i$$v_i$ 的 representation 向量，$d$$d$ 为 representation 向量的维度。

   一旦学到 $\mathbf{H}$$\mathbf H$ ，那么representation 向量就可以用于下游的任务，如节点分类任务。

   这里我们重点介绍图卷积编码器，它是一种灵活的node embedding 架构，并且通过在局部邻域上反复聚合从而生成节点representation 。

   一个关键结果是：生成的节点 embedding ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ summarize了节点 $v_i$$v_i$ 为中心的patch 的信息，而不仅仅是节点 $v_i$$v_i$ 本身。在下文中，我们用 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 来表示 patch representation 来强调这一点。

2. 我们学习编码器的方法依赖于最大化局部互信息（local mutual information），即：我们寻求节点的 representation（局部的），它捕获了整个图的全局信息内容（通过一个 summary vector $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ 来表示）。

   • 为了获得graph-level 的 summary vector $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ ，我们利用了一个 readout 函数 $\mathcal{R}:{\mathbb{R}}^{n\times d}\to {\mathbb{R}}^d$$\mathcal R:\mathbb R^{n\times d}\rightarrow \mathbb R^d$，并通过该函数将获得的 patch representation 总结为 graph-level representation ：$\overrightarrow{\mathbf{s}}=\mathcal{R}(\mathcal{E}(\mathbf{X},\mathbf{A}))$$\mathbf{\vec s}=\mathcal R\left(\mathcal E(\mathbf X,\mathbf A)\right)$ 。

   • 作为最大化局部互信息的代理proxy，我们使用了一个判别器（discriminator） $\mathcal{D}:{\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$$\mathcal D:\mathbb R^d\times \mathbb R^d\rightarrow \mathbb R$，其中 $\mathcal{D}({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})$$\mathcal D\left(\mathbf{\vec h}_i,\mathbf{\vec s}\right)$ 代表了patch-summary 的 pair 对之间的概率得分。如果 summary 包含这个 patch，则会返回一个更高的得分。

     • 判别器的正样本来自于 $\mathcal{G}=(\mathbf{X},\mathbf{A})$$\mathcal G=(\mathbf X,\mathbf A)$ 的patch representation 和 summary vector 的 pair 对 $\left\{({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})\right\}$$\left\{\left(\mathbf{\vec h}_i,\mathbf{\vec s}\right)\right\}$ 。

       注意，正样本来自于联合分布 $p({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})$$p\left(\mathbf{\vec h}_i,\mathbf{\vec s}\right)$ 。

     • 判别器的负样本来自于另一个图 $\tilde{\mathcal{G}}=(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$$\tilde{\mathcal G} = \left(\tilde{\mathbf X},\tilde{\mathbf A}\right)$ 的patch representation 和图 $\mathcal{G}=(\mathbf{X},\mathbf{A})$$\mathcal G=(\mathbf X,\mathbf A)$ 的 summary vector 的 pair 对 $\left\{({\widetilde{\overrightarrow{\mathbf{h}}}}_j,\overrightarrow{\mathbf{s}})\right\}$$\left\{\left(\tilde{\mathbf{\vec h}}_j,\mathbf{\vec s}\right)\right\}$ 。 其中 $\tilde{\mathbf{H}}=\mathcal{E}(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$$\tilde{\mathbf H}= \mathcal E\left(\tilde{\mathbf X},\tilde{\mathbf A}\right)$ 。

       在多图的环境下，可以将 $\tilde{\mathcal{G}}=(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$$\tilde{\mathcal G} = \left(\tilde{\mathbf X},\tilde{\mathbf A}\right)$ 选择为训练集中的其它图；在单图环境下，可以提供一个随机扰动函数 $\mathcal{C}:{\mathbb{R}}^{n\times d_f}\times {\mathbb{R}}^{n\times n}\to {\mathbb{R}}^{m\times d_f}\times {\mathbb{R}}^{m\times m}$$\mathcal C:\mathbb R^{n\times d_f}\times \mathbb R^{n\times n}\rightarrow \mathbb R^{m\times d_f}\times \mathbb R^{m\times m}$ 来获取 $(\tilde{\mathbf{X}},\tilde{\mathbf{A}})=\mathcal{C}(\mathbf{X},\mathbf{A})$$\left(\tilde{\mathbf X},\tilde{\mathbf A}\right)=\mathcal C(\mathbf X,\mathbf A)$ 。

       注意，负样本来自于边际分布乘积 $p\left({\overrightarrow{\mathbf{h}}}_i\right)p\left(\overrightarrow{\mathbf{s}}\right)$$p\left(\mathbf{\vec h}_i\right)p\left(\mathbf{\vec s}\right)$ 。

     负样本的选择将决定特定类型的结构信息，这些结构信息是作为这种互信息最大化的副产品而希望捕获的。

   • 我们遵循 Deep InfoMax: DIM 的直觉，使用对比噪音类型的目标函数（noise-contrastive type objective）：在联合分布（正样本）和边际概率乘积（负样本）之间应用标准的二元交叉熵（binary cross-entropy:BCE）损失。遵从DIM 的工作，我们使用以下目标函数：

     $$\mathcal{L}=\frac{1}{n+m}(\sum _{i=1}^n{\mathbb{E}}_{(\mathbf{X},\mathbf{A})}[\log \mathcal{D}({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})]+\sum _{j=1}^m{\mathbb{E}}_{(\tilde{\mathbf{X}},\tilde{\mathbf{A}})}[\log (1-\mathcal{D}({\widetilde{\overrightarrow{\mathbf{h}}}}_j,\overrightarrow{\mathbf{s}}))])$$

     基于联合分布与边际概率乘积之间的 JS 散度，该方法有效地最大化 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ 之间的互信息。

3. 由于迫使所有得到的 patch representation 都保持全局graph summary 的互信息，这使得可以保留 patch-level 的相似性。例如，具有相似结构角色（structural role）的距离遥远的节点（众所周知，这些节点是很多节点分类任务的强力的 predictor ）。

4. 假设在单图环境下，DGI 的过程如下图所示：

   • 使用随机扰动函数 $\mathcal{C}(\cdot ,\cdot )$$\mathcal C(\cdot,\cdot)$ 采样一个负样本：$(\tilde{\mathbf{X}},\tilde{\mathbf{A}})\sim \mathcal{C}(\mathbf{X},\mathbf{A})$$\left(\tilde{\mathbf X},\tilde{\mathbf A}\right)\sim \mathcal C(\mathbf X,\mathbf A)$ 。

     扰动函数的选择非常重要，可以仅扰动 $\mathbf{X}$$\mathbf X$ 而保留图结构、也可以仅扰动图结构 $\mathbf{A}$$\mathbf A$ 而保留节点特征、也可以二者同时扰动。

   • 通过编码器获取输入图 $\mathcal{G}$$\mathcal G$ 的 patch representation ：$\mathbf{H}=\mathcal{E}(\mathbf{X},\mathbf{A})$$\mathbf H = \mathcal E(\mathbf X,\mathbf A)$ 。

   • 通过编码器获取负样本 $\tilde{\mathcal{G}}$$\tilde{\mathcal G}$ 的 patch representation ：$\tilde{\mathbf{H}}=\mathcal{E}(\tilde{\mathbf{X}},\tilde{\mathbf{A}})$$\tilde{\mathbf H}=\mathcal E\left(\tilde{\mathbf X},\tilde{\mathbf A}\right)$ 。

   • 通过 readout 函数获取输入图 $\mathcal{G}$$\mathcal G$ 的 summary vector ：$\overrightarrow{\mathbf{s}}=\mathcal{R}(\mathbf{H})$$\mathbf{\vec s} = \mathcal R(\mathbf H)$ 。

   • 通过对损失函数 $\mathcal{L}$$\mathcal L$ 的梯度下降来更新 $\mathcal{E},\mathcal{R},\mathcal{D}$$\mathcal E,\mathcal R,\mathcal D$ 的参数。

   

1.2 定理

1. 现在我们提供一些直觉，将判别器 $\mathcal{D}$$\mathcal D$ 的分类误差和graph representation 上的互信息最大化联系起来。

2. 令 ${\left\{{\mathbf{X}}^{(k)}\right\}}_{k=1}^K$$\left\{\mathbf X^{(k)}\right\}_{k=1}^K$ 为从图的经验概率分布 $p(\mathbf{X})$$p(\mathbf X)$ 中抽样得到的 $K$$K$ 组node representation（每一组代表一个图，一共 $K$$K$ 个图） 。令 $\mathcal{R}(\cdot )$$\mathcal R(\cdot)$ 为图上的确定性的（非随机的）readout 函数，${\overrightarrow{\mathbf{s}}}^{(k)}=\mathcal{R}\left({\mathbf{X}}^{(k)}\right)$$\mathbf{\vec s}^{(k)}=\mathcal R\left(\mathbf X^{(k)}\right)$ 为第 $k$$k$ 个图的 summary vector，边际概率分布为 $p\left(\overrightarrow{\mathbf{s}}\right)$$p\left(\mathbf{\vec s}\right)$ 。假设类别平衡，则联合分布 $p(\mathbf{X},\overrightarrow{\mathbf{s}})$$p\left(\mathbf X,\mathbf{\vec s}\right)$ 和边际概率分布乘积 $p(\mathbf{X})p\left(\overrightarrow{\mathbf{s}}\right)$$p(\mathbf X)p\left(\mathbf{\vec s}\right)$ 之间的最优分类器的错误率的上限为：

   $${\text{Err}}^{\ast }=\frac{1}{2}\sum _{k=1}^{K}p{\left({\overrightarrow{\mathbf{s}}}^{(k)}\right)}^2$$

   当 $\mathcal{R}(\cdot )$$\mathcal R(\cdot)$ 是一个单射函数时可以达到该上限。

   证明见原始论文。

3. 可以证明：

   $$\frac{1}{2K}\le {\text{Err}}^{\ast }\le \frac{1}{2}$$

   其中：

   • 第一个不等式可以通过 Jensen 不等式来证明。

   • 第二个不等式当 readout 函数是一个常量时成立，此时没有任何分类器表现得比随机分类更好。

4. 推论：从现在开始，假设所使用的 readout 函数 $\mathcal{R}$$\mathcal R$ 是单射的。假设 $\overrightarrow{\mathbf{s}}$$\mathbf{\vec s}$ 的状态空间数量为 $S$$S$ （即 $K$$K$ 个图得到的、不同的 summary vector 数量）满足 $S\ge K$$S\ge K$ 。则对于在联合分布和边际概率乘积之间的最优分类器的分类误差下的最优 summary ${\overrightarrow{\mathbf{s}}}^{\ast }$$\mathbf{\vec s}^*$ 满足：$S=K$$S =K$ 。

   证明见原始论文。

5. 定理一：记MI 为互信息，则有 ${\overrightarrow{\mathbf{s}}}^{\ast }=\arg \underset{\overrightarrow{\mathbf{s}}}{max}\text{MI}(\mathbf{X};\overrightarrow{\mathbf{s}})$$\mathbf{\vec s}^* = \arg\max_{\mathbf{\vec s}} \text{MI}\left(\mathbf X;\mathbf{\vec s}\right)$ 。

   证明见原始论文。

   该定理表明：对于有限的输入集和合适的确定性函数，可以通过最小化判别器中的分类误差来最大化输入和输出之间的互信息。

6. 定理二：令 ${\mathbf{X}}_i^{(k)}={\left\{{\overrightarrow{\mathbf{x}}}_j\right\}}_{j\in {\mathcal{N}}_{k,i}}$$\mathbf X_i^{(k)}=\left\{\mathbf{\vec x}_j\right\}_{j\in \mathcal N_{k,i}}$ 为第 $k$$k$ 个图中的节点 $v_i$$v_i$ 的邻居特征矩阵，${\mathcal{N}}_{k,i}$$\mathcal N_{k,i}$ 为第 $k$$k$ 个图中的节点 $v_i$$v_i$ 的邻域。令 $\mathcal{E}$$\mathcal E$ 为一个确定性（即不是随机的）的编码器函数，第 $k$$k$ 个图中的节点 $v_i$$v_i$ 的 high-level 特征为： ${\overrightarrow{\mathbf{h}}}_i=\mathcal{E}\left({\mathbf{X}}_i^{(k)}\right)$$\mathbf{\vec h}_i=\mathcal E\left(\mathbf X_i^{(k)}\right)$ 。

   假设有 $|{\mathbf{X}}_i|=|\mathbf{X}|=\left|\overrightarrow{\mathbf{s}}\right|\ge \left|{\overrightarrow{\mathbf{h}}}_i\right|$$|\mathbf X_i| = |\mathbf X| =\left |\mathbf{\vec s}\right|\ge \left|\mathbf{\vec h}_i\right|$ ，其中 $|\cdot |$$|\cdot|$ 为取值集合的大小。则 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 如果最小化 $p({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})$$p\left(\mathbf{\vec h}_i,\mathbf{\vec s}\right)$ 和 $p\left({\overrightarrow{\mathbf{h}}}_i\right)p\left(\overrightarrow{\mathbf{s}}\right)$$p\left(\mathbf{\vec h}_i\right)p\left(\mathbf{\vec s}\right)$ 之间的分类误差，则它也最大化 $\text{MI}({\mathbf{X}}_i^{(k)},{\overrightarrow{\mathbf{h}}}_i)$$\text{MI}\left(\mathbf X_i^{(k)},\mathbf{\vec h}_i\right)$ 。

   证明见原始论文。

   这激发了我们在联合分布和边际概率乘积的样本之间使用分类器，并且在神经网络优化的上下文下，使用 binary cross-entropy:BCE 损失来优化该分类器。

1.3 实验

1. 我们评估了 DGI 编码器在各种节点分类任务（transductive learning 和 inductive learning ）上学到的 representation 的优势。

   在每种情况下，都是用 DGI 以完全无监督方式学到了patch representation ，然后用简单的线性（逻辑回归）分类器来进行node-level 分类。分类器的输入就是节点的 representation 。

2. 数据集：

   • 引文网络 Cora, Citeseer, Pubmed：它们是 transductive learning 数据集。在这些数据集中，节点表示论文，边表示论文之间的引用关系，节点特征对应于论文的 bag-of-word 。每个节点都有一个类别标签。

     我们对每个类别仅允许使用 20 个节点进行训练。但是，为了遵循transductive learning，无监督学习算法可以访问所有节点的特征向量。

     我们在 1000 个测试节点上评估了学到representation 的预测能力。

   • Reddit 数据集：它是大图上的 inductive learning 数据集。我们使用 2014 年9 月期间创建的 Reddit 帖子作为数据集，每个帖子代表节点，如果同一个用户对两个帖子都发表了评论则这两个帖子之间存在边。

     数据集包含 231443 个节点、11606919 条边。节点特征是帖子内容和评论的 GloVe embedding 向量、以及帖子的评分或者评论数量等指标。我们的目标是预测帖子所属的社区。

     我们将前20 天发布的帖子用于训练、剩余帖子用于验证或测试。并且训练期间，验证集和测试集是不可见的。

   • PPI 数据集：它是多图的 inductive learning 数据集。该数据集由不同人体组织对应的graph 组成，其中包含 20 个图用于训练、2 个图用于验证、2 个图用于测试。注意，在训练过程中，测试图完全未被观察到。

     每个节点具有 50 个特征，这些特征由 positional gene sets, motif gene sets, immunological signatures 等组成。一个节点可能具有多个标签，这些标签是从分子本体数据库收集的基因本体标签，共有 121 个。

   所有数据集的统计信息如下表。

   

1.3.1 配置

1. 我们对于 transductive learning、单图inductive learning、多图 inductive learning 使用不同的编码器和扰动函数。

2. transductive learning：我们使用单层GCN 作为编码器，即：

   $$\mathcal{E}(\mathbf{X},\mathbf{A})=\sigma \left({\hat{\mathbf{D}}}^{-1/2}\hat{\mathbf{A}}{\hat{\mathbf{D}}}^{-1/2}\mathbf{X}\mathbf{W}\right)$$

   其中：

   • $\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\hat{\mathbf A} = \mathbf A + \mathbf I$ 为带自环的邻接矩阵，$\hat{\mathbf{D}}$$\hat{\mathbf D}$ 为对应的度矩阵（它是一个对角矩阵，满足 ${\hat{D}}_{i,i}=\sum _j{\hat{A}}_{i,j}$$\hat D_{i,i} = \sum_j\hat A_{i,j}$）。

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数，这里我们使用参数化的 ReLU （即 parametric ReLU: PReLU）。

   • $\mathbf{W}\in {\mathbb{R}}^{d_f\times d}$$\mathbf W\in \mathbb R^{d_f\times d}$ 为待学习的参数矩阵。这里我们选择 $d=512$$d = 512$。对于 Pubmed 数据集，由于内存限制我们选择 $d=256$$d = 256$ 。

   这里使用的扰动函数旨在鼓励representation 正确编码图中不同节点的结构相似性，因此 $\mathcal{C}$$\mathcal C$ 保留了原始的邻接矩阵，即 $\tilde{\mathbf{A}}=\mathbf{A}$$\tilde{\mathbf A} = \mathbf A$ 。而扰动的特征 $\tilde{\mathbf{X}}$$\tilde{\mathbf X}$ 是对 $\mathbf{X}$$\mathbf X$ 进行按行混洗得到的。即扰动的图由原始图中完全相同的节点组成，但是节点位于图中的不同位置，因此接收不同的 patch representation 。

   论文证明了DGI 对于其它扰动函数是稳定的（参考原始论文），但是我们发现：保留图结构的那些扰动函数效果最好。

3. 单图inductive learning：这里我们不再使用单层 GCN 作为编码器，因为这种编码器依赖于固定且已知的邻接矩阵。相反，我们使用 GraphSAGE-GCN，并选择均值池化：

   $$\text{MP}(\mathbf{X},\mathbf{A})={\hat{\mathbf{D}}}^{-1}\hat{\mathbf{A}}\mathbf{X}\mathbf{W}$$

   这里通过度矩阵 $\hat{\mathbf{D}}$$\hat{\mathbf D}$ 进行了归一化，实际上也可以通过 GAT 模型来编码。

   我们的编码器采用三层GraphSAGE-GCN，并使用 skip connection ：

   $$\begin{array}{c}\widetilde{\text{MP}}(\mathbf{X},\mathbf{A})=\sigma (\mathbf{X}{\mathbf{W}}^{\prime }||\text{MP}(\mathbf{X},\mathbf{A}))\\ \mathcal{E}(\mathbf{X},\mathbf{A})={\widetilde{\text{MP}}}_3({\widetilde{\text{MP}}}_2({\widetilde{\text{MP}}}_1(\mathbf{X},\mathbf{A}),\mathbf{A}),\mathbf{A})\end{array}$$

   其中 $||$$||$ 表示特征拼接。

   • 这里我们选择 $d=512$$d = 512$，并且选择 $\sigma (\cdot )$$\sigma(\cdot)$ 为 PReLU 激活函数。

   • 考虑到Reddit 数据集规模较大，无法完全放入GPU 内存。这里我们采用 GraphSAGE 中的采样方法：分别在第一层、第二层、第三层对邻域采样 10/10/25 个邻居节点。因此每个中心节点将采样 1+10+100+2500=2611 个3-hop 邻域节点（称作一个 patch）。

   • 在整个训练过程中，我们使用了 batch-size=256 的 mini-batch 随机梯度下降。

   • 我们使用和 transductive learning 中类似的扰动函数，但是将每个采样的 patch 视为要扰动的子图。注意，这可能导致中心节点的特征被替换为采样邻居的特征，从而进一步促进了负样本的多样性。然后将中心节点的 patch representation 馈入到判别器。

4. 多图 inductive learning ：我们的编码器是一个三层的GraphSAGE 均值池化模型，并且带skip connection：

   $$\begin{array}{c}{\mathbf{H}}_1=\sigma ({\text{MP}}_1(\mathbf{X},\mathbf{A}))\\ {\mathbf{H}}_2=\sigma ({\text{MP}}_2({\mathbf{H}}_1+\mathbf{X}{\mathbf{W}}_{\text{skip}},\mathbf{A}))\\ \mathcal{E}(\mathbf{X},\mathbf{A})=\sigma ({\text{MP}}_3({\mathbf{H}}_2+{\mathbf{H}}_1+\mathbf{X}{\mathbf{W}}_{\text{skip}},\mathbf{A}))\end{array}$$

   其中 ${\mathbf{W}}_{\text{skip}}$$\mathbf W_{\text{skip}}$ 为待学习的参数矩阵。这里和单图inductive learning 区别在于：这里的 skip connection 是sum 融合，而前述的 skip connection 是 concate 融合。

   • 这里我们选择 $d=512$$d = 512$，并且选择 $\sigma (\cdot )$$\sigma(\cdot)$ 为 PReLU 激活函数。

   • 在多图环境下，我们选择使用随机采样的训练graph 来作为负样本。即我们的扰动函数只是从训练集中采样了不同的图。考虑到该数据集中 40% 以上的节点包含全零的特征，因此这种方法最为稳定。

   • 为进一步扩大负样本的范围，我们还对采样的graph 的输入特征应用 dropout 。

   • 我们还发现将学到的embedding 馈入到逻辑回归模型之前，对包括训练集上的embedding 进行标准化是有益的。

5. 在所有的配置下，我们使用统一的readout 函数、判别器架构：

   • 我们使用简单的均值函数来作为readout 函数：

     $$\mathcal{R}(\mathbf{H})=\sigma \left(\frac{1}{n}\sum _{i=1}^n{\overrightarrow{\mathbf{h}}}_i\right)$$

     其中 $\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 非线性函数。

     尽管我们发现该readout 函数在所有实验中表现最佳，但是我们假设其能力会随着graph size 的增加而降低。此时，可能需要使用更复杂的readout 架构，如 set2vec 或者 DiffPool 。

   • 判别器通过应用简单的双线性评分函数对 summary-patch 进行评分：

     $$\mathcal{D}({\overrightarrow{\mathbf{h}}}_i,\overrightarrow{\mathbf{s}})=\sigma \left({\overrightarrow{\mathbf{h}}}_i^{\mathrm{\top }}{\mathbf{W}}_D\overrightarrow{\mathbf{s}}\right)$$

     其中 ${\mathbf{W}}_D$$\mathbf W_D$ 为待学习的参数矩阵，$\sigma (\cdot )$$\sigma(\cdot)$ 为 sigmoid 非线性激活函数。

6. 所有模型都使用 Glorot 初始化，并使用 Adam SGD 优化器进行训练，初始学习率为 0.001（对于 Reddit 为 ${10}^{-5}$$10^{-5}$ ）。

7. 在 transductive 数据集上，我们在training loss 上应用早停策略，patience epoch = 20 。在 inductive 数据集上，我们训练固定数量的 epoch，对于 Reddit 为 150、对于 PPI 为 20 。

1.3.2 结果

1. baseline 方法：

   • transductive learning：我们进行了 50 次实验并报告测试集上的平均准确率和标准差。然后将我们的结果和 DeepWalk, GCN, Label Propagation:LP, Planetoid 等方法进行比较。

     另外我们还提供了对原始特征进行逻辑回归分类、将原始特征和 DeepWalk 特征拼接进行逻辑回归分类的结果。

   • inductive learning：我们进行了 50 次实验并报告了测试集上的 micro-F1 得分的均值。我们直接复用 GraphSAGE 论文中的结果进行比较。

     由于我们的方法是无监督的，因此我们对比了无监督的 GraphSAGE 方法。

     我们还提供了两种监督学习的方法比较：FastGCN 和 Avg. pooling 。

2. 实验结果如下表所示，其中第一列中我们给出每种方法在训练过程中可用的数据类型：X 为特征信息，A 为邻接矩阵，Y 为标签信息。GCN 对应于以监督方式训练的两层 DGI 编码器。

   结论：

   • DGI 在所有五个数据集上均实现了出色的性能。尤为注意的是，DGI 方法和监督学习的 GCN 模型相比具有竞争力，并且在 Cora 数据集和 Citeseer 数据集上甚至超越了监督学习的 GCN 。

     我们认为这些优势源自事实：DGI 方法间接地允许每个节点都可以访问整个图的属性，而监督学习的 GCN 仅限于两层邻域（由于训练信号的极其稀疏，因此可能会遭受过拟合的风险）。

     应当指明的是，尽管我们能够超越同等编码器架构的监督学习，但是我们我们的性能仍然无法超越 SOTA 的 transductive 架构。

   • DGI 方法在 Reddit 和 PPI 数据集上成功超越了所有竞争的无监督 GraphSAGE 方法，从而验证了 inductive learning 节点分类任务中，基于局部互信息最大化方法的潜力。

     DGI 在 Reddit 上的结果和监督学习的 SOTA 相比具有竞争力，而在 PPI 上差距仍然很大。我们认为这可以归因于节点可用特征的极度稀疏：在 PPI 数据集上超过 40% 的节点具有全零特征。而我们的 DGI 方法中的编码器非常依赖于节点特征。

   • 我们注意到，随机初始化的图卷积网络（不需要经过训练）可能已经提取了非常有用的特征，并代表了强大的 baseline。这是众所周知的事实，因为它和 WL test 图同构测试有关。这已被GCN 和 GraphSAGE 等论文所研究过。

     为此，我们提供了 Random-Init 这个 baseline，它是从随机初始化的编码器（不需要训练）获取节点 embedding，然后馈入逻辑回归分类器。

     • DGI 可以在这个强大的 baseline 上进一步提升。

     • 在 inductive 数据集上的结果表明：以前基于随机游走的负采样方法可能对于学习分类任务是无效的。

     这个编码器其实就是 GCN/GraphSAGE 等常用架构。

   • 最后，应该注意的是，更深的编码器减少了我们正负样本之间的有效变异性。我们认为这就是为什么浅层架构在某些数据集上表现更好的原因。虽然我们不能说这个趋势普遍存在，但是通过 DGI 损失函数我们发现，通常采用更 wider 的模型而不是更 deeper 的模型可以带来收益。

   

3. 定性分析：我们给出 Cora 数据集的 embedding 经过 t-SNE 可视化结果（因为该数据集节点数最少）。左图为原始特征的可视化，中间为Random-Init 得到 embedding 的可视化，右图为训练好的 DGI 得到 embedding 的可视化。

   可以看到：DGI 得到的embedding 的投影表现出明显的聚类。

   

4. 在t-SNE 可视化之后，我们关注Cora 数据集上判别器的得分。我们对于正样本和负样本（随机采样的）可视化了每个节点的判别器得分：左图为正样本（真实的图）、右图为负样本（负采样的图）。

   可以看到：

   • 在正样本学到的 embedding 的簇上，只有少数 hot 节点得到较高的判别器得分。这表明用于判别和分类的 embedding 各维度之间可能存在明显的差异。

   • 正如预期的那样，模型无法在负样本中找到任何强大的结构。

   • 一些负样本种的节点获得了较高的判别器得分，这是由于 Cora 中的一些 low-degree 节点引起的。

     正样本的平均分高于负样本的平均分。

   

5. 我们将判别器打分 top-score 的正样本和负样本的 embedding 进行可视化。如下图所示：上半部分为 highest-scored 正样本，下半部分为 lowerst-scored 负样本。

   可以看到：在某些维度上，正样本和负样本都存在着严重的 bias。

   我们假设：在随机shuffle $\mathbf{X}$$\mathbf X$ 的情况下，负样本的平均预期激活值为零，因此需要强大的bias 需要将负样本的判别器得分拉下来。对于正样本，可以使用其它维度来抵消这些维度上的 bias ，同时编码 patch 相似度。

   

   为证明这一假设，我们根据正样本和负样本之间的可区分性对 512 个维度进行排序。我们从 embedding 中根据该顺序依次删除这些维度（要么从最有区分度的维度开始，记作 $p\uparrow$$p\uparrow$；要么是从最没有区分度的维度开始，记作 $p\downarrow$$p\downarrow$ ） ，然后检测分类器和判别器的性能，结果如下图所示。

   可以看到，观察到的趋势在很大程度上支持了我们的假设：如果我们首先删除 biased 维度（$p\downarrow$$p\downarrow$），则分类效果会保持更长的时间（允许我们删除一半以上的 embedding 维度，同时仍保持对监督 GCN 的竞争优势）。正样本仍然能够保持正确的判别，直到移除了一半以上的维度为止。

   注意：biased 维度指的是正样本和负样本都存在着严重的 bias的维度，因此无法区分正样本和负样本。